package com.lei.leetcode;

/**
 * @Author LeiXiaoLei
 * @Date 2022/8/12 10:40
 * @Version 1.0
 */
public class S_75 {
    private void swap(int[] nums, int i, int j) {
        int num = nums[i];
        nums[i] = nums[j];
        nums[j] = num;
    }

    public void sortColors(int[] nums) {
        int l = -1, r = nums.length, i = 0;
        while (i < r)
            if (nums[i] == 0)
                swap(nums, ++l, i++);
            else if (nums[i] == 2)
                swap(nums, i, --r);
            else
                i++;
    }

    public void sortColors2(int[] nums) {
        int R = 3;
        int[] cnt = new int[R];
        for (int num : nums) {
            cnt[num]++;
        }
        int[] index = new int[R + 1];
        for (int i = 0; i < R; i++) {
            index[i + 1] = index[i] + cnt[i];
        }
        for (int i = 0; i + 1 < index.length; i++) {
            for (int j = index[i]; j < index[i + 1]; j++) {
                nums[j] = i;
            }
        }
    }
}
